{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Split Array Into Maximum Number of Subarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #bit-manipulation #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #位运算 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSubarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将数组分割成最多数目的子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个只包含 <strong>非负</strong>&nbsp;整数的数组&nbsp;<code>nums</code>&nbsp;。</p>\n",
    "\n",
    "<p>我们定义满足 <code>l &lt;= r</code>&nbsp;的子数组&nbsp;<code>nums[l..r]</code>&nbsp;的分数为&nbsp;<code>nums[l] AND nums[l + 1] AND ... AND nums[r]</code>&nbsp;，其中&nbsp;<strong>AND</strong>&nbsp;是按位与运算。</p>\n",
    "\n",
    "<p>请你将数组分割成一个或者更多子数组，满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>每个</strong> 元素都&nbsp;<strong>只</strong>&nbsp;属于一个子数组。</li>\n",
    "\t<li>子数组分数之和尽可能<strong>&nbsp;小</strong>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你在满足以上要求的条件下，返回<strong>&nbsp;最多</strong>&nbsp;可以得到多少个子数组。</p>\n",
    "\n",
    "<p>一个 <strong>子数组</strong>&nbsp;是一个数组中一段连续的元素。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,0,2,0,1,2]\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>我们可以将数组分割成以下子数组：\n",
    "- [1,0] 。子数组分数为 1 AND 0 = 0 。\n",
    "- [2,0] 。子数组分数为 2 AND 0 = 0 。\n",
    "- [1,2] 。子数组分数为 1 AND 2 = 0 。\n",
    "分数之和为 0 + 0 + 0 = 0 ，是我们可以得到的最小分数之和。\n",
    "在分数之和为 0 的前提下，最多可以将数组分割成 3 个子数组。所以返回 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [5,7,1,3]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>我们可以将数组分割成一个子数组：[5,7,1,3] ，分数为 1 ，这是可以得到的最小总分数。\n",
    "在总分数为 1 的前提下，最多可以将数组分割成 1 个子数组。所以返回 1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [split-array-into-maximum-number-of-subarrays](https://leetcode.cn/problems/split-array-into-maximum-number-of-subarrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [split-array-into-maximum-number-of-subarrays](https://leetcode.cn/problems/split-array-into-maximum-number-of-subarrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,2,0,1,2]', '[5,7,1,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre = nums.copy()\n",
    "        for i in range(1, n):\n",
    "            pre[i] &= pre[i - 1]\n",
    "        final = pre[-1]\n",
    "        cnt = 0\n",
    "        while len(nums) != 0:\n",
    "            cnt += 1\n",
    "            x = nums.pop()\n",
    "            while len(nums) != 0 and pre[len(nums) - 1] + x > final:\n",
    "                x &= nums.pop()\n",
    "            final -= x\n",
    "        return cnt\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        t = reduce(and_, nums)\n",
    "        if t:\n",
    "            return 1\n",
    "        s, t = 0, nums.pop()\n",
    "        while True:\n",
    "            while t:\n",
    "                if not nums:\n",
    "                    return s\n",
    "                t &= nums.pop()\n",
    "            s += 1\n",
    "            if not nums:\n",
    "                return s\n",
    "            t = nums.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        target = reduce(operator.and_, nums)\n",
    "        if target != 0:\n",
    "            return 1\n",
    "        t = -1\n",
    "        ans = 0\n",
    "        while nums:\n",
    "            t &= nums.pop()\n",
    "            if t == target:\n",
    "                ans += 1\n",
    "                t = -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        pre = -1\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            pre = pre & nums[i]\n",
    "            if(pre == 0 ):\n",
    "                ans += 1\n",
    "                pre = -1\n",
    "        if(ans == 0):\n",
    "            return 1\n",
    "        else:\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        pre = 16777215\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            pre = pre & nums[i]\n",
    "            if(pre == 0 ):\n",
    "                ans += 1\n",
    "                pre = 16777215\n",
    "        if(ans == 0):\n",
    "            return 1\n",
    "        else:\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        tgt = nums[0]\n",
    "        n = len(nums)\n",
    "        loc = 0\n",
    "        ans = 0\n",
    "        while loc < n:\n",
    "            tmp = nums[loc]\n",
    "            loc += 1\n",
    "            while loc < n and tmp:\n",
    "                tmp = tmp&nums[loc]\n",
    "                loc += 1\n",
    "            if not tmp:\n",
    "                ans += 1\n",
    "        if not ans:\n",
    "            return 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        a = -1\n",
    "        count = 0\n",
    "        for i in nums:\n",
    "            a &= i\n",
    "            if a == 0:\n",
    "                count += 1\n",
    "                a = -1\n",
    "        return count if count!=0 else 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        tgt = reduce(operator.and_, nums)\n",
    "        if tgt!=0: return 1\n",
    "        res = 0\n",
    "        tmp = None\n",
    "        for x in nums:\n",
    "            tmp = x if tmp is None else tmp & x\n",
    "            if tmp==tgt:\n",
    "                res += 1\n",
    "                tmp = None\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        a = -1  # -1 就是 111...1，和任何数 AND 都等于那个数\n",
    "        for x in nums:\n",
    "            a &= x\n",
    "            if a == 0:\n",
    "                ans += 1  # 分割\n",
    "                a = -1\n",
    "        return max(ans, 1)  # 如果 ans=0 说明所有数的 and>0，答案为 1\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        i, j = 0 , len(nums) -1\n",
    "        ans = 0 \n",
    "        r = None\n",
    "        for n in nums:\n",
    "            if not r:\n",
    "                r = n\n",
    "            else:\n",
    "                r = r & n\n",
    "            if r == 0:\n",
    "                ans+=1\n",
    "                r = None\n",
    "        if ans == 0:\n",
    "            return 1\n",
    "        return ans \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = -1\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            ans &= num\n",
    "            if ans == 0:\n",
    "                cnt += 1\n",
    "                ans = -1\n",
    "        return max(cnt, 1)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        while(i < n):\n",
    "            cur = nums[i]\n",
    "            i+=1\n",
    "            while(i < n and cur != 0):\n",
    "                cur &= nums[i]\n",
    "                i+=1\n",
    "            if(cur==0):\n",
    "                ans += 1\n",
    "        \n",
    "        return max(ans,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        x = -1\n",
    "        ans = 0\n",
    "        for i in nums:\n",
    "            x &= i\n",
    "            if x == 0:\n",
    "                ans+=1\n",
    "                x = -1\n",
    "        return max(ans,1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        target = reduce(lambda x, y : x & y, nums)\n",
    "        if target != 0:\n",
    "            return 1\n",
    "\n",
    "        ans = 0\n",
    "        cur = -1\n",
    "        for n in nums:\n",
    "            cur &= n\n",
    "            if cur == target:\n",
    "                ans += 1\n",
    "                cur = -1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        a = -1  # -1 就是 111...1，和任何数 AND 都等于那个数\n",
    "        for x in nums:\n",
    "            a &= x\n",
    "            if a == 0:\n",
    "                ans += 1  # 分割\n",
    "                a = -1\n",
    "        return max(ans, 1)  # 如果 ans=0 说明所有数的 and>0，答案为 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        score = nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            score &= nums[i]\n",
    "        \n",
    "        if score!=0:\n",
    "            return 1\n",
    "        \n",
    "        ret = 0\n",
    "        cur = None\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            n = nums[i]\n",
    "            if cur==None:\n",
    "                cur = n\n",
    "            else:\n",
    "                cur &= n\n",
    "            \n",
    "            if cur==0:\n",
    "                ret += 1\n",
    "                cur = None\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "\n",
    "        def awy(the_list: List[int]):\n",
    "            res = -1\n",
    "            for i in range(len(the_list)):\n",
    "                res &= the_list[i]\n",
    "            return res\n",
    "\n",
    "        res = 0\n",
    "        lingshi = []\n",
    "        if awy(nums) != 0:\n",
    "            return 1\n",
    "        for i in range(len(nums)):\n",
    "            lingshi.append(nums[i])\n",
    "            if awy(lingshi) == 0 or nums[i] == 0:\n",
    "                res += 1\n",
    "                lingshi = []\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        cur = -1\n",
    "        for v in nums:\n",
    "            cur&=v\n",
    "            if cur==0:\n",
    "                cur = -1\n",
    "                res += 1\n",
    "        return max(1,res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        a = -1  # -1 就是 111...1，和任何数 AND 都等于那个数\n",
    "        for x in nums:\n",
    "            a &= x\n",
    "            if a == 0:\n",
    "                ans += 1  # 分割\n",
    "                a = -1\n",
    "        return max(ans, 1)  # 如果 ans=0 说明所有数的 and>0，答案为 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        # nums [l, r] AND  \n",
    "        target = reduce(iand, nums)\n",
    "        print(target)\n",
    "        cnt = 0\n",
    "        s = nums[0]\n",
    "        for x in nums[1:]:\n",
    "            if s == target:\n",
    "                cnt += 1\n",
    "                s = x\n",
    "            else:\n",
    "                s &= x\n",
    "        if s == target: cnt += 1\n",
    "        return cnt if target == 0 else 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        cur = nums[0]\n",
    "        for i in nums[1:]:\n",
    "            if cur:\n",
    "                cur &= i\n",
    "            else:\n",
    "                cur = i\n",
    "                ans += 1\n",
    "        if not cur:\n",
    "            ans += 1\n",
    "        return ans if ans > 0 else 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return 1\n",
    "        ans = 0\n",
    "        min_num = nums[0]\n",
    "        for num in nums[1:]:\n",
    "            min_num &= num\n",
    "        if min_num >= 1:\n",
    "            return 1\n",
    "        s = -1\n",
    "        pre = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if s < 0:\n",
    "                s = num\n",
    "                pre = i\n",
    "            if s >= 0 and s == min_num:\n",
    "                ans += 1\n",
    "                s = -1\n",
    "            else:\n",
    "                if i != pre:\n",
    "                    s &= num  \n",
    "                    if s >= 0 and s == min_num:\n",
    "                        ans += 1\n",
    "                        s = -1\n",
    "        return ans\n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        min_total = nums[0]\n",
    "        for n in nums:\n",
    "            min_total &= n\n",
    "        res = 0\n",
    "        #print(min_total)\n",
    "        cur = int(\"11111111111111111111111111111111\",2)\n",
    "        for n in nums:\n",
    "            cur &= n\n",
    "            print(n, cur)\n",
    "            if cur == 0:\n",
    "                res += 1\n",
    "                cur = int(\"11111111111111111111111111111111\",2)\n",
    "        if res == 0:\n",
    "            res = 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        s = 0\n",
    "        cur = nums[0]\n",
    "        nums = nums + [-1]\n",
    "        tem = nums[0]\n",
    "        for i in range(len(nums)):\n",
    "            cur &= nums[i]\n",
    "            tem &= nums[i]\n",
    "            if cur == 0:\n",
    "                s += 1\n",
    "                cur = nums[i + 1]\n",
    "        return s if tem == 0 else 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        5   101\n",
    "        7.  111\n",
    "        3.  011\n",
    "        1.  001\n",
    "        \n",
    "        与的话, 长度越长, 结果越小\n",
    "        对于某个已经检测到的和, 如果要保持和不变, 并且增加子数组数目, 那么增加的子数组内与的结果必须是0\n",
    "        \n",
    "        所以, 先把数组内所有的数与一遍, 就能得到最小的分数之和, 也就是最终分数\n",
    "        然后再遍历一遍, 直到分数为最终分数\n",
    "        \n",
    "        然后开始遍历\n",
    "        '''\n",
    "        ALL =  (1 << 32) -1\n",
    "        andres = ALL\n",
    "        \n",
    "        for x in nums:\n",
    "            andres = andres & x\n",
    "        \n",
    "        if andres > 0:\n",
    "            return 1\n",
    "        \n",
    "        cnt = 0\n",
    "        andres = ALL\n",
    "        for x in nums:\n",
    "            andres = x & andres\n",
    "            if andres == 0:\n",
    "                cnt += 1\n",
    "                andres = ALL\n",
    "        \n",
    "        return cnt\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        t = nums[0]\n",
    "        for i in range(1, n):\n",
    "            t &= nums[i]\n",
    "        if t != 0:\n",
    "            return 1\n",
    "        ans = 0\n",
    "        t = nums[0]\n",
    "        for i in range(n):\n",
    "            t &= nums[i]\n",
    "            if t & nums[i] == 0:\n",
    "                ans += 1\n",
    "                if i != n - 1:\n",
    "                    t = nums[i + 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        def score(left, right):\n",
    "            res = nums[left]\n",
    "            for i in range(left, right + 1):\n",
    "                res = res & nums[i]\n",
    "            return res\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "        all_score = score(0, len(nums) - 1)\n",
    "        if all_score != 0:\n",
    "            return 1\n",
    "        before = nums[0]\n",
    "        now = before\n",
    "        for i, x in enumerate(nums):\n",
    "            before = before & x\n",
    "            print(i, before)\n",
    "\n",
    "            \n",
    "            if before == 0:\n",
    "                ans += 1\n",
    "                if i != len(nums) - 1:\n",
    "                    before = nums[i + 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrays(self, nums: List[int]) -> int:\n",
    "        tmp = -1\n",
    "        ans = 0\n",
    "        for i in nums:\n",
    "            if tmp == -1:\n",
    "                tmp = i\n",
    "            else:\n",
    "                tmp = tmp & i\n",
    "            if tmp == 0:\n",
    "                ans += 1\n",
    "                tmp = -1\n",
    "        return ans if ans else 1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
